1. Field of the Invention
The present invention relates to a fast Fourier transform (FFT) system, and more particularly, to an effective memory address generating apparatus and method for implementing a calculation module of a fast Fourier transform (FFT).
2. Description of the Background Art
In general, according to a Fourier theorem that one signal can be expressed as the sum of an infinite number of sinusoidal signals, a signal in the time domain or the frequency domain can be transformed to the corresponding domain through a Fourier transform and an inverse Fourier transform.
A discrete Fourier transform (DFT) transforms a discrete temporal signal expressed as a linear combination of sinusoidal signals having different frequencies into a frequency domain signal of sinusoidal signals and magnitude, which is widely adopted in a digital signal analysis and their fields of application.
A fast Fourier transform (FFT), devised to reduce the complexity of the discrete Fourier transform (DFT), is an algorithm minimizing calculation complexity by using a symmetry characteristic of the discrete Fourier transform when the number of input samples is the square value of ‘2’. This algorithm is widely used as a practical application of the discrete Fourier transform.
The fast Fourier transform is divided into a decimation in frequency (DIF) algorithm and a decimation in time (DIT) algorithm depending on a derivation method of a formula, and the DIT algorithm, which is widely used, will be mainly described in the present invention.
FIG. 1 is an exemplary view showing the data flow of a so called “bufterfly”, the basic computational element of the FFT and a corresponding calculation formula.
As shown in FIG. 1, the calculation result of the butterfly operation is expressed as follows:             X      t1        =                  X        s1            +                        exp          ⁢                      (                                                            -                  j2                                ⁢                                                                  ⁢                π                ⁢                                                                  ⁢                K                            N                        )                          ⁢                  X          s2                                X      t2        =                  X        s1            -                        exp          ⁢                      (                                                            -                  j2                                ⁢                                                                  ⁢                π                ⁢                                                                  ⁢                K                            N                        )                          ⁢                  X          s2                    wherein Xs1 and Xs2 are two input data, Xt1 and Xt2 are two output data, ‘K’ is a parameter of the butterfly calculation, and ‘N’ is the total number of input samples.
FIG. 2 is an exemplary view showing the signal flow of an 8-point FFT using the DIT algorithm.
As shown in FIG. 2, the FFT is formed as the basic calculation unit of a butterfly operation, and each butterfly operation is performed according to a stage.
The FFT calculation method will now be described.
First, time domain input data is stored according to a predetermined order. At this time, the input data storing order is that an input data index is represented as a binary number and the order of the value is reversed, which is called a bit reversed addressing.
Thereafter, the inputted data is processed according to the butterfly calculation determined for each stage like the flow of data as shown in FIG. 2 and an FFT is performed.
At this time, the calculated frequency domain output data of the FFT is stored in ascending order from ‘0’ and outputted, unlike the input data.
However, the FFT method still suffers from many problems with respect to an algorithm operation for implementing faster and more effective hardware in spite of being effective compared to the DFT method.
A method for implementing the FFT algorithm at a high speed will now be taken as an example.
M. C. Pease (M. C. Pease, “Organization of large scale Fourier processors” J. Assoc. Comput. Mach. Vol. 16, pp. 474–482, July 1969) has proposed a memory operating method that concurrently reads and writes a memory for a fast processing speed. This method stores mutually different input/output data of the butterfly calculation operation in different memory banks (a divided memory unit) in order to concurrently read and write them.
FIG. 3 is a signal flow chart showing a memory bank index extraction in the FFT calculation.
As shown in FIG. 3, in this method, orders are given to each line of a signal flow from ‘0’ in turn and data is stored in a memory bank corresponding to the parity of the order value (if the number ‘1’ bits in a binary number is an even number, its parity is ‘0’, while if it is an odd number, its parity is ‘1’).
Accordingly, the whole data are divided and stored in two memory banks, and an input and an output of the butterfly operation are mutually different memory banks over the entire stage.
Meanwhile, D. Cohen (D. Cohen, “simplified control of FFT hardware” IEE Trans. Acoust., Speech Signal Processing, vol. ASSP-24, pp. 577–579, Dec. 1976) and L. G. Johnson (L. G. Johnson, “Conflict free memory addressing for dedicate FFT hardware” IEEE Trans. Circuits Syst. II, vol. 39, pp 312–316, May 1992) have proposed a fast and effective FFT hardware implementing method on the basis of the memory operating method such as in FIG. 3.
However, in case of such method, the index calculation of the memory bank uses the general parity calculation method. Thus, if the size of the FFT is increased, there is a large delay time in calculating a parity, so that this method is not suitable for implementing a fast FFT hardware.
In addition, Y. Ma (Y. Ma, “An effective memory addressing scheme for FFT processors,” IEEE Trans. Signal Processing, vol.47, pp. 907–911, March 1999) and L. Wanhammar (Y. Ma and L. Wanhammar, “A Hardware Efficient Control of Memory Addressing for High-Performance FFT processors,” IEEE Trans. Signal Processing, vol. 48, No.3, March 2000) have proposed a fast FFT memory operating method in which the calculation of a bank index is fast and simple, instead of using an in-place method (an input and an output of calculation are stored in the same position) such as in the aforementioned method proposed by M. C Peace.
However, this method has problems in that it is difficult to implement an algorithm, a register is additionally required besides a given memory since it does not employ the in-place method, and an FFT structure of a pipeline method is necessarily used, causing a latency time.